import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.*;

import java.util.stream.Collectors;

/**
 * 139. 单词拆分
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
 *
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 */
public class WordsSplit {

    @Test
    public void test1() {
        Assertions.assertTrue(wordBreak("leetcode", Arrays.asList("leet", "code")));
    }

    @Test
    public void test2() {
        Assertions.assertTrue(wordBreak("applepenapple", Arrays.asList("apple", "pen")));
    }

    @Test
    public void test3() {
        Assertions.assertFalse(wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat")));
    }

    @Test
    public void test4() {
        Assertions.assertTrue(wordBreak("aaaaaaa", Arrays.asList("aaaa", "aaa")));
    }

    @Test
    public void test5() {
        Assertions.assertTrue(wordBreak("bccdbacdbdacddabbaaaadababadad", Arrays.asList("cbc", "bcda", "adb", "ddca", "bad", "bbb", "dad", "dac", "ba", "aa", "bd", "abab", "bb", "dbda", "cb", "caccc", "d", "dd", "aadb", "cc", "b", "bcc", "bcd", "cd", "cbca", "bbd", "ddd", "dabb", "ab", "acd", "a", "bbcc", "cdcbd", "cada", "dbca", "ac", "abacd", "cba", "cdb", "dbac", "aada", "cdcda", "cdc", "dbc", "dbcb", "bdb", "ddbdd", "cadaa", "ddbc", "babb")));
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        /*
         * 从 s[0] 到 s[i] 能否由 wordDict 中的字符组成
         * */
        boolean[] composableArray = new boolean[s.length() + 1];

        // s[0] 到 s[0] 可由 wordList 组成
        composableArray[0] = true;

//       根据 wordList 中每个字符的长度来进行分组
        Map<Integer, List<String>> wordLengthMappingWordList = wordDict.stream().collect(Collectors.groupingBy(String::length, Collectors.toList()));

        for (int i = 1; i < composableArray.length; i++) {

            for (int composableIndex = i - 1; composableIndex >= 0; composableIndex--) {


                if (composableArray[composableIndex]) {
//                  从 composableArray[i] 向 composableArray[0] 寻找每一个可组合 的位置

//                  找到  wordList 中 长度符合 其中一个 composableIndex 到 i 的word
                    List<String> wordCandidateList = wordLengthMappingWordList.get(i - composableIndex);

                    if (wordCandidateList == null) {
                        continue;
                    }

                    for (String candidate : wordCandidateList) {

                        if (Objects.equals(candidate, s.substring(composableIndex, i))) {
//                            字符串匹配成功，标记这个 composableIndex 为可组合的
                            composableArray[i] = true;
                            break;
                        }
                    }
                }
            }
        }


        return composableArray[composableArray.length - 1];
    }
}
